package cover.alg;


import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultEdge;

import cover.vertex.Vertex;

/**
 * Heuristic Vertex Crossover
 * To get child from two parents
 *
 */

public class HVX {
	
	private Set<Vertex> parent1;
	private Set<Vertex> parent2;
	private Graph<Vertex, DefaultEdge> graph;
	private Set<Vertex> child;
	
	public HVX(Set<Vertex> parent1,Set<Vertex> parent2, 
			Graph<Vertex, DefaultEdge> graph) {
		this.parent1 = parent1;
		this.parent2 = parent2;
		this.graph = Utils.copyOfGraph(graph);
		this.child = new HashSet<Vertex>();
	}
	/**
	 * Heuristic Vertex Crossover Operator
	 * 
	 * @return child
	 */
	public Set<Vertex> makeChild(){
		LinkedList<VertexField> vertexTable = getVertexTable();
		while(!graph.edgeSet().isEmpty()){
			VertexField tempVertex = (VertexField)vertexTable.removeFirst();
			child.add(tempVertex.getVertex());
			for(Vertex vertex : Graphs.neighborListOf(graph,tempVertex.getVertex())){
				graph.removeAllEdges(tempVertex.getVertex(),vertex);
			}
		}
		return child;
	}
	/**
	 * VT = (F(v), N(v)), where F(v) is the frequency of the vertex v in P1 and P2,
	 * N(v) is the degree of vertex v in G, for every v in P1 and every v in P2
	 * 
	 * @return
	 */
	private LinkedList<VertexField> getVertexTable(){
		LinkedList<VertexField> vertexTable = new LinkedList<VertexField>();
		Set<Vertex> vertices = graph.vertexSet();
		for (Vertex vertex : vertices) {
			if(graph.edgesOf(vertex).isEmpty())
				continue;
			int frequency = 0;
			if (parent1.contains(vertex))
				frequency++;
			if (parent2.contains(vertex))
				frequency++;
			VertexField newField = new VertexField(vertex,frequency,Graphs.neighborListOf(graph,vertex).size());
			if (frequency!=0){
				if(vertexTable.isEmpty())
					vertexTable.add(newField);
				else{
					for(int i = 0;i < vertexTable.size();i++){
						if(vertexTable.get(i).getDegree() < newField.getDegree()){
							vertexTable.add(i,newField);
							break;
						}
						else if(vertexTable.get(i).getDegree() == newField.getDegree() && 
							vertexTable.get(i).getFrequency() < newField.getFrequency()){						
							vertexTable.add(i,newField);
							break;
						}
						else if(i == vertexTable.size() - 1){
							vertexTable.addLast(newField);
							break;
						}
					}
				}
			}
			else vertexTable.add(newField);
		}
		return vertexTable;
	}
	
	public Set<Vertex> getChild() {
		return child;
	}
}
